package linkedlist.leetcode_86_medium;

public class Partition {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(-1);
        ListNode other = new ListNode(-1);

        ListNode s = small;
        ListNode o = other;
        while(head != null){
            if(head.val < x){
                s.next = head;
                s = s.next;
            }else{
                o.next = head;
                o = o.next;
            }
            head = head.next;
        }
        s.next = other.next;
        o.next = null;
        return small.next;
    }
}
